import java.util.List;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class project {
    public int pairSum(ListNode head) {
        ListNode left=head;
        ListNode right=head;
        while (right!=null&&right.next!=null){
            left=left.next;
            right=right.next.next;
        }
        ListNode prev=null;
        ListNode cur=left;
        while (cur!=null){
            ListNode curNext=cur.next;
            cur.next=prev;
            prev=cur;
            cur=curNext;
        }
        int max=0;
        left=head;
        right=prev;
        while (right!=null){
            max=Math.max(left.val+right.val,max);
            left=left.next;
            right=right.next;
        }
        return max;
    }





























    public int findCircleNum(int[][] isConnected) {
        int len=isConnected.length;
        boolean[] booleans=new boolean[len];
        int count=0;
        for(int i=0;i<len;i++){
            if(booleans[i]==false){
                dfs(i,len,booleans,isConnected);
                count++;
            }
        }
        return count;
    }
    public void dfs(int i,int len,boolean[] booleans,int[][] arr){
        for(int j=0;j<len;j++){
            if(arr[i][j]==1&&booleans[j]==false){
                booleans[j]=true;
                dfs(j,len,booleans,arr);
            }
        }
    }




















    public int findCircleNum1(int[][] isConnected) {
        int len=isConnected.length;
        boolean[] booleans=new boolean[len];
        int count=0;
        for(int i=0;i<len;i++){
            if(!booleans[i]){
                dfs(i,len,booleans,isConnected);
                count++;
            }
        }
        return count;
    }
    public void dfs1(int i,int len,boolean[] booleans,int[][] arr){
        for(int j=0;j<len;j++){
            if(!booleans[j]){
                booleans[j]=true;
                dfs(j,len,booleans,arr);
            }
        }
    }
}
